翻訳と辞書 Words near each other ・ Solothurn S-18/100 ・ Solothurn S-18/1000 ・ Solothurn S-18/1100 ・ Solothurn ST-5 ・ Solothurn thaler ・ Solothurn-Arsenal ・ Solothurner Literaturpreis ・ SoloTrek XFV ・ Solotuša ・ Solotvyn ・ Solotvyno ・ Solouk Duo ・ Solovair ・ Solovar ・ Solovay model ・ Solovay–Strassen primality test ・ Soloveitchik ・ Solovetsky ・ Solovetsky (rural locality) ・ Solovetsky District ・ Solovetsky Islands ・ Solovetsky Monastery ・ Solovetsky Monastery Uprising ・ Solovetsky Stone ・ Solovetsky, Arkhangelsk Oblast ・ Solovey (surname) ・ Solovey iz sela Marshintsy ・ Soloviev D-20 ・ Soloviev D-25 ・ Soloviev D-30 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Solovay–Strassen primality test ： ウィキペディア英語版 Solovay–Strassen primality test The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. It has been largely superseded by the Baillie-PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. ==Concepts== Euler proved〔Euler's criterion〕 that for any prime number ''p'' and any integer ''a'', :$a^\; \backslash equiv\; \backslash left(\backslash frac\backslash right)\; \backslash pmod\; p$ where $\backslash left(\backslash tfrac\backslash right)$ is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to $\backslash left(\backslash tfrac\backslash right)$, where ''n'' can be any odd integer. The Jacobi symbol can be computed in time O((log ''n'')²) using Jacobi's generalization of law of quadratic reciprocity. Given an odd number ''n'' we can contemplate whether or not the congruence :$a^\; \backslash equiv\; \backslash left(\backslash frac\backslash right)\; \backslash pmod\; n$ holds for various values of the "base" ''a'', given that ''a'' is relatively prime to ''n''. If ''n'' is prime then this congruence is true for all ''a''. So if we pick values of ''a'' at random and test the congruence, then as soon as we find an ''a'' which doesn't fit the congruence we know that ''n'' is not prime (but this does not tell us a nontrivial factorization of ''n''). This base ''a'' is called an ''Euler witness'' for ''n''; it is a witness for the compositeness of ''n''. The base ''a'' is called an ''Euler liar'' for ''n'' if the congruence is true while ''n'' is composite. For every composite odd ''n'' at least half of all bases :$a\; \backslash in\; (\backslash mathbb/n\backslash mathbb)^$ * are (Euler) witnesses:〔(PlanetMath )〕 this contrasts with the Fermat primality test, for which the proportion of witnesses may be much smaller. Therefore, there are no (odd) composite ''n'' without many witnesses, unlike the case of Carmichael numbers for Fermat's test. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Solovay–Strassen primality test」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.